package william.tree;

import java.util.ArrayList;
import java.util.Collections;
import java.util.LinkedList;
import java.util.List;

/**
 * @author ZhangShenao
 * @date 2024/1/15
 * @description <a href="https://leetcode.cn/problems/binary-tree-preorder-traversal/description/">...</a>
 */
public class Leetcode144_二叉树的前序遍历 {
    private class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode() {
        }

        TreeNode(int val) {
            this.val = val;
        }

        TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }

    public List<Integer> preorderTraversal(TreeNode root) {
        //边界条件校验
        if (root == null) {
            return Collections.emptyList();
        }

        List<Integer> result = new ArrayList<>();

        //递归处理
        preorderTraversalRecursive(root, result);

        //返回结果
        return result;
    }


    /**
     * 递归前序遍历
     */
    private void preorderTraversalRecursive(TreeNode root, List<Integer> result) {
        //递归终止条件
        if (root == null) {
            return;
        }

        //首先访问根节点
        result.add(root.val);

        //然后遍历左子树
        preorderTraversalRecursive(root.left, result);

        //最后遍历右子树
        preorderTraversalRecursive(root.right, result);
    }

    private class Command {
        /**
         * 命令类型
         * traversal=遍历
         * visit=访问当前节点
         */
        private String type;

        /**
         * 执行命令的节点
         */
        private TreeNode node;

        public Command(String type, TreeNode node) {
            this.type = type;
            this.node = node;
        }
    }


    /**
     * 迭代版本,借助栈实现
     * 将遍历操作封装成一个个命令,压入栈中。然后依次从栈中弹出命令执行
     * 压栈的命令顺序依次为: 遍历右子树 -> 遍历左子树 -> 访问当前节点
     * <p>
     * 时间复杂度O(N) 遍历树一次
     * 空间复杂度O(N) 额外申请了一个栈,大小为树的长度
     */
    /*public List<Integer> preorderTraversal(TreeNode root) {
        //边界条件校验
        if (root == null) {
            return Collections.emptyList();
        }

        //借助一个栈,保存待执行的命令
        LinkedList<Command> stack = new LinkedList<>();

        List<Integer> result = new ArrayList<>();

        //首先将遍历根节点的命令入栈
        stack.push(new Command("traversal", root));

        //依次从栈中弹出命令执行
        while (!stack.isEmpty()) {
            Command cmd = stack.pop();
            if ("visit".equals(cmd.type)) {  //访问当前节点
                result.add(cmd.node.val);
                continue;
            }

            //遍历操作
            //压栈的命令顺序依次为: 遍历右子树 -> 遍历左子树 -> 访问当前节点
            if (root.right != null) {
                stack.push(new Command("traversal", root.right));
            }
            if (root.left != null) {
                stack.push(new Command("traversal", root.left));
            }
            stack.push(new Command("visit", root));
        }


        //返回结果
        return result;
    }*/
}
